\subsubsection{Solución elegida}
Como mencionamos en la seccion Ideas se eligio realizar un Backtracking con las fichas añadiendose podas.
Estas podas son operaciones sobre las fichas para evitar probar casos o extenderse por ramas de casos que sabemos que no son solucion.

\subsubsection{Definiciones}
Se realizaron las siguientes definiciones para el desarrollo del algoritmo:
Estructura Ficha:
	- ID
	- Base
	- Altura 
	- Rotacion
	- Matriz colores
    - cantNegras
Descripcion de la estructura Ficha:
- ID es un Entero, representa el numero de ficha en el orden que se ingreso en el archivo.
- Base es un Entero, representa el valor de la base ingresada en el archivo de la ficha
- Altura es un Entero, representa el valor de la altura ingresada en el archivo de la ficha	
- La Mariz representa la ficha en si, contiene los numeros 0 y 1 que representan cada color de las posiciones,  esta representado con 
   un vector de vectores de enteros cada posicion del vector principal es una fila y adentro contiene un vector que representa las columnas
- cantNegras indica la cantida de posiciones negras que tiene el tablero

Estructura Tablero :
	- base; 
	- altura;
	- matriz posiciones; 
	- matriz usadas; 
	- cantLibres; 
	- cantNegras; 

Descripcion de la estructura Ficha:
- Base es un Entero, representa el valor de la base ingresada en el archivo del tablero
- Altura es un Entero, representa el valor de la altura ingresada en el archivo del tablero
- La Mariz posiciones representa el tablero en si, contiene los numeros 0 o 1 que representan cada color de las posiciones,  esta representado con 
   un vector de vectores de enteros cada posicion del vector principal es una fila y adentro contiene un vector que representa las columnas
- La Mariz usadas representa el tablero en si, contiene los numeros 0 o 2 que indica si esta utilizada la posicion con un 2 y si esta vacia con un 0,
  esta representado con un vector de vectores de enteros cada posicion del vector principal es una fila y adentro contiene un vector que representa las columnas
-  cantLibres es un entero indica la cantidad de posiciones que todavia no fueron ocupadas en el tablero
- cantNegras es un entero que indica la cantidad de posiciones negras que todavia estan libres
Y por ultimo la Estructura Posiciones:
	- id; 
	-  r; 
	- x; 
	- y; 
	- fic;
Esta estructura esta usada para la salida que representa lo siguiente:
- ID es un entero que indica el numero de ficha de la estructura ficha
- R es un entero que indica la rotacion en la que se coloco la ficha
- x es un entero que indica la posicion X en la matriz del tablero en donde se coloco
- y es un entero que representa la posicion Y en la matriz del tablero en donde se coloco
- fic es la ficha en si se que guardo en ese lugar.

\subsubsection{Algoritmo de resolucion}
    El algoritmo de Backtracking para la solucion del tablero realiza dos podas iniciales para quitar algunos casos, cada poda consiste el ciclar las fichas que se tienen en el momento y ver
	si la cantidad de posiciones libres del tableros indicadas por $cantLibres$ es mayor a la cantidad de posiciones que va a ocupar la ficha y si la cantida de posiciones negras que tiene la 
	ficha $cantNegras$ es mayor a la cantidad de posiciones negras libres que tiene el tablero $cantNegras$.
	Luego en el caso que no haya mas posiciones libres en el tablero $cantLibres$ entonces se completo el tablero de manera exitosa y termino la recursion, de lo contrario consultamos si seguimos teniendo
	fichas disponibles para colocar y en este caso no se puede termino de completar el tablero y no tiene solucion por ese camino.
	Luego realizamos un ciclo sobre las fichas y para cada una realizamos un ciclo definiendo el angulo de rotacion, en este caso realizamos una poda preguntando para saber si la ficha no queda fuera del tablero
	en caso que entre la ficha y que no quede fuera del tablero consultamos mediante una funcion para probar la ficha en el tablero que devuelve los siguientes resultados
	- devuelve 0 si la ficha es solucion y hace retornar a la funcion de backtracking un valor exitoso y termina con el hilo de recursion
	- devuelve 1 si la ficha entra en la posicion en la que estamos ubicados y faltan fichas para completar el tablero, este saca la ficha del conjunto de fichas y vuelve a llamar a la recursion, revisa que resultado da
	  la llamada recursiva, si devuelve verdadero, termina el hilo de recursion es porque se encontro solucion, caso contrario quita la ficha del tablero y sigue probando con las rotaciones.
	- devuelve 2 si la ficha no entra por un tema de colores pero los colores son los mismos que hay en la posicion y sigue probando rotandola
	- devuelve 3 si la ficha no entra en esa posicion y sigue probando rotandola una vez mas, si la ficha no entra en la segunda rotacion realizamos una poda aca.
	
El tipo $Tablero$ es $Tupla \langle base:\ Int,\ altura:\ Int, cantLibres:\ Int,\ cantNegras:\ int,\ colores: Matriz\langle Int\rangle,\ usadas: Matriz\langle Int\rangle \rangle$.

El tipo $Ficha$ es $Tupla \langle id:\ Int,\ rotacion:\ Int,\ base:\ Int,\ altura:\ Int,\ puntos:\ Matriz\langle Int\rangle,\ cantNegras:\ int \rangle$.

El tipo $Ficha$ es $Tupla \langle id:\ Int,\ r:\ Int,\ x:\ Int,\ y:\ Int,\ fic:\ Ficha \rangle$.

\begin{pseudocode}[ruled]{PuzzleDeCasilleros}{Tablero tab, Secuencia\langle Ficha\rangle \; fichero, Secuencia\langle Posiciones\rangle \; pos}

	\LOCAL x \GETS 0\\
	\LOCAL y \GETS 0\\
	\LOCAL Secuencia \langle Nat \rangle V1 \\ \\

	\FOR i \GETS 0 \TO tab.altura(puntos) \\ \DO
	\BEGIN
		V1.erase(V1.begin(),V1.end()) \\
		\FOR j \GETS 0 \TO tab.base \\ \DO
			V1.push_back(0) \\				
		tab.usadas.push_back(v1);
	\END \\
	\LOCAL res \GETS \CALL{backtrack}{tab,k,fichero,pos,x,y}\\	
	\OUTPUT{res}

\end{pseudocode}\\

{\fontsize{5}{5}\selectfont
\begin{pseudocode}[ruled]{backtrack}{Tablero tab, Int K, Secuencia\langle Ficha\rangle \: fichero, Secuencia\langle Posiciones\rangle :\ pos, Int : \&x,Int \&y}
	\LOCAL res \GETS false\\
    \LOCAL vector<ficha> copiaFichero \GETS fichero\\
	
	//borro todas las que son mas grandes que el tablero\\ \\
    
	\FOR i \GETS 0 \TO Tamanio(copiaFichero) - 1 \\ \DO
		\IF copiaFichero[i].base*copiaFichero[i].altura > tab.cantLibres || copiaFichero[i].cantNegras > tab.cantNegras \THEN
				copiaFichero.erase(copiaFichero.begin() + i); \\ \\
   
	\LOCAL newK \GETS copiaFichero.size()\\

	\IF tab.cantLibres == 0 \THEN
		\RETURN{TRUE}\\
	\ELSE \IF newK==0 \THEN
		\RETURN {FALSE}
		\ELSE 
		    \BEGIN	
			\LOCAL newx \GETS x\\
			\LOCAL newy \GETS y\\ \\

	\FOR i \GETS 0 \TO newK - 1 \\ \DO
	\BEGIN        
		proximo:\\
		\LOCAL Ficha f1 \GETS copiaFichero[i]\\
		
		\FOR j \GETS 0 \TO 3 \\ \DO
		\BEGIN
			\LOCAL Posiciones p\\
			\IF ($f1.base+x <= tab.base \&\& f1.altura+y <= tab.altura$) \THEN
			\BEGIN
	      			\IF probar(tab,f1,newx,newy) == 0 \THEN
				\BEGIN
					f1.rotacion \GETS j\\
					p.id \GETS f1.id\\
		        		p.fic \GETS f1\\
					p.r \GETS f1.rotacion\\
					p.x \GETS x\\
					p.y \GETS y\\
					pos.push_back(p)\\
					actualizar(tab,pos,newx,newy)\\
		               		newK \GETS newk - 1\\
		                	\RETURN{TRUE}\\
				\END \\ \\
				\IF probar(tab,f1,newx,newy) == 1 \THEN
				\BEGIN
					f1.rotacion \GETS j\\
		        		p.fic \GETS f1\\
					p.r \GETS f1.rotacion\\
					p.id \GETS f1.id\\
					p.x \GETS x\\
					p.y \GETS y\\
					pos.push_back(p)\\
					actualizar(tab,pos,newx,newy)\\
		               		newK \GETS newk - 1\\
					copiaFichero.erase(copiaFichero.begin()+i)\\
					res \GETS \\ \CALL{backtrack}{tab,newK,copiaFichero,pos,newx,newy}\\
					\IF res == TRUE \THEN				
						\RETURN{TRUE}
					\ELSE
						\BEGIN
							\CALL{desactualizar}{tab,pos,newx,newy}\\
							f1 \GETS pos.back.fic\\
							newK \GETS newK + 1\\
							pos.pop_back()\\
							i \GETS i + 1\\
							\IF i >= newk \THEN				
								\RETURN{FALSE}
							\ELSE goto proximo\\
						\END
					
				\END \\	 \\
				\IF probar(tab,f1,newx,newy) == 2 \THEN			
		           		\CALL{rotar}{f1}\\
					continuar\\
				\IF probar(tab,f1,newx,newy) == 3 \THEN	
				\BEGIN
					\IF j<2 \THEN	
						\CALL{rotar}{f1}\\
					\ELSE
						goto proximo\\
				\END \\
			\END \\
			\ELSE
				\IF j<2 \THEN
					\CALL{rotar}{f1}\\
				\ELSE break\\
		\END \\	\\
		\END \\ \\
       \RETURN{res} \\
     \END


\end{pseudocode}
}

\begin{pseudocode}[ruled]{Actualizar}{Tablero tab, Secuencia\langle Posiciones\rangle \; pos,\ Int x, Int y}

	\LOCAL Posiciones p \GETS pos.back\\

	\FOR i \GETS y \TO y+p.fic.altura - 1 \\ \DO
		\FOR j \GETS y \TO y+p.fic.altura - 1 \\ \DO
			tab.usadas[i][j] \GETS 2\\ \\
	
	tab.cantLibres \GETS tab.cantLibres - p.fic.base*p.fic.altura\\
	tab.cantNegras \GETS tab.cantNegras - p.fic.cantNegras\\

	\LOCAL i \GETS x\\
	\LOCAL j \GETS y\\

	\WHILE tab.usadas[j][i]!=0 \DO
		\BEGIN
			i \GETS i + 1\\
			\IF i==tab.base \THEN
			\BEGIN
				i \GETS 0\\
				j \GETS j +1\\		
				\IF j==tab.altura \THEN
					break\\
			\END \\
		\END \\ \\
	x \GETS i\\
	y \GETS j\\
                         
\end{pseudocode}\\

\begin{pseudocode}[ruled]{Desactualizar}{Tablero tab, Secuencia\langle Posiciones\rangle \; pos,\ Int x, Int y}

	\LOCAL Posiciones p \GETS pos.back\\

	\FOR i \GETS p.y \TO p.y+p.fic.altura - 1 \\ \DO
		\FOR j \GETS p.x \TO p.x + p.fic.base - 1 \\ \DO
			tab.usadas[i][j] \GETS 0\\ \\
	
	tab.cantLibres \GETS tab.cantLibres + p.fic.base*p.fic.altura\\
	tab.cantNegras \GETS tab.cantNegras + p.fic.cantNegras\\

	\LOCAL x \GETS p.x\\
	\LOCAL y \GETS p.y\\

	\WHILE tab.usadas[j][i]!=0 \DO
		\BEGIN
			i \GETS i + 1\\
			\IF i==tab.base \THEN
			\BEGIN
				i \GETS 0\\
				j \GETS j +1\\		
				\IF j==tab.altura \THEN
					break\\
			\END \\
		\END \\ \\
	x \GETS i\\
	y \GETS j\\
                         
\end{pseudocode}\\

\begin{pseudocode}[ruled]{Rotar}{Ficha f1}
	\LOCAL vector<vector<int> > res\\
	\LOCAL vector<vector<int> > v1\\
	\LOCAL filas \GETS f1.altura\\
	\LOCAL columnas \GETS f1.base\\

	\FOR i \GETS columnas-1 DOWN\TO 0 \DO
	\BEGIN		
		v1.erase(v1.begin(),v1.end())\\		
		\FOR j \GETS 0 \TO filas - 1 \\ \DO
			v1.push_back(f1.puntos[j][i]) \\
		res.push_back(v1)\\
	\END

	f1.puntos \GETS res\\

    \LOCAL newaltura \GETS f1.base\\
    f1.base \GETS f1.altura\\
    f1.altura \GETS newaltura\\
                         
\end{pseudocode}\\

\begin{pseudocode}[ruled]{Probar}{Tablero tab,Ficha fi, int x, int y}
	\LOCAL cantNegras \GETS 0\\
	\FOR j \GETS y \TO fi.altura+y -1 \DO
		\FOR i \GETS x \TO fi.base+x - 1 \\ \DO
		\BEGIN
			\IF tab.usadas[j][i] == 2 \THEN \RETURN{3}\\
			\IF tab.usadas[j][i] == 0 \THEN \RETURN{cantNegras++}\\
		\END \\
	\IF cantNegras != fi.cantNegras \THEN \RETURN{3} \\
	\LOCAL fix \GETS 0 \\
	\LOCAL fiy \GETS 0 \\
	\FOR j \GETS y \TO fi.altura+y - 1 \\ \DO
	\BEGIN
		fix \GETS 0\\
		\FOR i \GETS x \TO fi.base+x - 1 \\ \DO
		\BEGIN
			\IF tab.colores[j][i] != fi.puntos[fiy][fix] \THEN \RETURN{2} \\
                      	fix \GETS fix + 1\\
		\END
	\END
	\IF tab.usadas[j][i] == 2 \THEN \RETURN{0}\\
	\ELSE \RETURN{1}\\

\end{pseudocode}

	
	



